package com.zy.recursion;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @description: 杨辉三角
 * @author: zhaoyi
 * @create: 2019-09-03 21:37
 * https://leetcode-cn.com/explore/orignial/card/recursion-i/257/recurrence-relation/1202/
 **/

public class YangHuiTriangle {

    //递归一定注意避免重复计算
    private Map<String, Integer> map;


    /**
     * 输入: 5
     * 输出:
     * [
     * [1],
     * [1,1],
     * [1,2,1],
     * [1,3,3,1],
     * [1,4,6,4,1]
     * ]
     *
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList(numRows);
        int length = ((numRows + 1) * numRows)/2;
        map = new HashMap(length,1);
        for (int y = 0; y < numRows; y++) {
            List ls = new ArrayList(y + 1);
            for (int x = 0; x <= y; x++) {
                ls.add(function(x, y));
            }
            list.add(ls);
        }
        return list;
    }

    private int function(int x, int y) {
        String key = x + "_" + y;
        Integer value = map.get(key);
        if (value != null) {
            return value;
        } else {
            if (x == 0 || x == y) {
                return 1;
            } else {
                int i = function(x - 1, y - 1) + function(x, y - 1);
                map.put(key, i);
                return i;
            }
        }
    }


    /**
     * 输入: 3
     * 输出: [1,3,3,1]
     * 你可以优化你的算法到 O(k) 空间复杂度吗？
     *  目前的方式空间复杂的
     *      1 + 2 + 3 + n 等差数列和空间复杂度n平方
     * https://leetcode-cn.com/explore/orignial/card/recursion-i/257/recurrence-relation/1203/
     *
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<Integer>(rowIndex + 1);
        int length = ((rowIndex + 2) * (rowIndex + 1))/2;
        map = new HashMap(length,1);
        for (int i = 0; i < rowIndex + 1; i++) {
            list.add(function(i,rowIndex));
        }
        return list;
    }


}
